/*

   Red Black Trees

   (C) 1999  Andrea Arcangeli <andrea@suse.de>


   This program is free software; you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation; either version 2 of the License, or

   (at your option) any later version.



   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.



   You should have received a copy of the GNU General Public License

   along with this program; if not, write to the Free Software

   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA



   To use rbtrees you'll have to implement your own insert and search cores.

   This will avoid us to use callbacks and to drop drammatically performances.

   I know it's not the cleaner way,  but in C (not in C++) to get

   performances and genericity...



   Some example of insert and search follows here. The search is a plain

   normal search over an ordered tree. The insert instead must be implemented

   int two steps: as first thing the code must insert the element in

   order as a red leaf in the tree, then the support library function

   rb_insert_color() must be called. Such function will do the

   not trivial work to rebalance the rbtree if necessary.



   -----------------------------------------------------------------------

   static inline struct page * rb_search_page_cache(struct inode * inode,

   unsigned long offset)

   {

   rb_node_t * n = inode->i_rb_page_cache.rb_node;

   struct page * page;



while (n)

{

    page = rb_entry(n, struct page, rb_page_cache);



    if (offset < page->offset)

        n = n->rb_left;

    else if (offset > page->offset)

        n = n->rb_right;

    else

        return page;

}

return NULL;

}



static inline struct page * __rb_insert_page_cache(struct inode * inode,

        unsigned long offset,

        rb_node_t * node)

{

    rb_node_t ** p = &inode->i_rb_page_cache.rb_node;

    rb_node_t * parent = NULL;

    struct page * page;



    while (*p)

    {

        parent = *p;

        page = rb_entry(parent, struct page, rb_page_cache);



        if (offset < page->offset)

            p = &(*p)->rb_left;

        else if (offset > page->offset)

            p = &(*p)->rb_right;

        else

            return page;

    }



    rb_link_node(node, parent, p);



    return NULL;

}



static inline struct page * rb_insert_page_cache(struct inode * inode,

        unsigned long offset,

        rb_node_t * node)

{

    struct page * ret;

    if ((ret = __rb_insert_page_cache(inode, offset, node)))

        goto out;

    rb_insert_color(node, &inode->i_rb_page_cache);

out:

    return ret;

}

-----------------------------------------------------------------------

teawater:This file is come from the Linux Kernel.

*/



#ifndef _LINUX_RBTREE_H

#define _LINUX_RBTREE_H



typedef struct rb_node_s {

    struct rb_node_s * rb_parent;

    int rb_color;

#define RB_RED      0

#define RB_BLACK    1

    struct rb_node_s * rb_right;

    struct rb_node_s * rb_left;

}rb_node_t;



typedef struct rb_root_s {

    struct rb_node_s * rb_node;

}rb_root_t;



#define RB_ROOT             (rb_root_t){ NULL, }

#define rb_entry(ptr, type, member) ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))





static inline void

rb_link_node(rb_node_t * node, rb_node_t * parent, rb_node_t ** rb_link)

{

    node->rb_parent = parent;

    node->rb_color = RB_RED;

    node->rb_left = node->rb_right = NULL;



    *rb_link = node;

}



static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
{
    rb_node_t * right = node->rb_right;

    if ((node->rb_right = right->rb_left))
        right->rb_left->rb_parent = node;
    right->rb_left = node;

    if ((right->rb_parent = node->rb_parent))
    {
        if (node == node->rb_parent->rb_left)
            node->rb_parent->rb_left = right;
        else
            node->rb_parent->rb_right = right;
    }
    else
        root->rb_node = right;
    node->rb_parent = right;
}



static void __rb_rotate_right(rb_node_t * node, rb_root_t * root)
{
    rb_node_t * left = node->rb_left;

    if ((node->rb_left = left->rb_right))
        left->rb_right->rb_parent = node;
    left->rb_right = node;

    if ((left->rb_parent = node->rb_parent))
    {
        if (node == node->rb_parent->rb_right)
            node->rb_parent->rb_right = left;
        else
            node->rb_parent->rb_left = left;
    }
    else
        root->rb_node = left;
    node->rb_parent = left;
}


static void rb_insert_color(rb_node_t * node, rb_root_t * root)
{
    rb_node_t * parent, * gparent;

    while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
    {
        gparent = parent->rb_parent;

        if (parent == gparent->rb_left)
        {
            {
                register rb_node_t * uncle = gparent->rb_right;
                if (uncle && uncle->rb_color == RB_RED)
                {
                    uncle->rb_color = RB_BLACK;
                    parent->rb_color = RB_BLACK;
                    gparent->rb_color = RB_RED;
                    node = gparent;
                    continue;
                }
            }

            if (parent->rb_right == node)
            {
                register rb_node_t * tmp;
                __rb_rotate_left(parent, root);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            parent->rb_color = RB_BLACK;
            gparent->rb_color = RB_RED;
            __rb_rotate_right(gparent, root);
        }
        else
        {
            {
                register rb_node_t * uncle = gparent->rb_left;
                if (uncle && uncle->rb_color == RB_RED)
                {
                    uncle->rb_color = RB_BLACK;
                    parent->rb_color = RB_BLACK;
                    gparent->rb_color = RB_RED;
                    node = gparent;
                    continue;
                }
            }

            if (parent->rb_left == node)
            {
                register rb_node_t * tmp;
                __rb_rotate_right(parent, root);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            parent->rb_color = RB_BLACK;
            gparent->rb_color = RB_RED;
            __rb_rotate_left(gparent, root);
        }
    }

    root->rb_node->rb_color = RB_BLACK;
}


static void __rb_erase_color(rb_node_t * node, rb_node_t * parent, rb_root_t * root)
{
    rb_node_t * other;

    while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
    {
        if (parent->rb_left == node)
        {
            other = parent->rb_right;
            if (other->rb_color == RB_RED)
            {
                other->rb_color = RB_BLACK;
                parent->rb_color = RB_RED;
                __rb_rotate_left(parent, root);
                other = parent->rb_right;
            }
            if ((!other->rb_left ||
                        other->rb_left->rb_color == RB_BLACK)
                    && (!other->rb_right ||
                        other->rb_right->rb_color == RB_BLACK))
            {
                other->rb_color = RB_RED;
                node = parent;
                parent = node->rb_parent;
            }
            else
            {
                if (!other->rb_right ||
                        other->rb_right->rb_color == RB_BLACK)
                {
                    register rb_node_t * o_left;
                    if ((o_left = other->rb_left))
                        o_left->rb_color = RB_BLACK;
                    other->rb_color = RB_RED;
                    __rb_rotate_right(other, root);
                    other = parent->rb_right;
                }
                other->rb_color = parent->rb_color;
                parent->rb_color = RB_BLACK;
                if (other->rb_right)
                    other->rb_right->rb_color = RB_BLACK;
                __rb_rotate_left(parent, root);
                node = root->rb_node;
                break;
            }
        }
        else
        {
            other = parent->rb_left;
            if (other->rb_color == RB_RED)
            {
                other->rb_color = RB_BLACK;
                parent->rb_color = RB_RED;
                __rb_rotate_right(parent, root);
                other = parent->rb_left;
            }
            if ((!other->rb_left ||
                        other->rb_left->rb_color == RB_BLACK)
                    && (!other->rb_right ||
                        other->rb_right->rb_color == RB_BLACK))
            {
                other->rb_color = RB_RED;
                node = parent;
                parent = node->rb_parent;
            }
            else
            {
                if (!other->rb_left ||
                        other->rb_left->rb_color == RB_BLACK)
                {
                    register rb_node_t * o_right;
                    if ((o_right = other->rb_right))
                        o_right->rb_color = RB_BLACK;
                    other->rb_color = RB_RED;
                    __rb_rotate_left(other, root);
                    other = parent->rb_left;
                }
                other->rb_color = parent->rb_color;
                parent->rb_color = RB_BLACK;
                if (other->rb_left)
                    other->rb_left->rb_color = RB_BLACK;
                __rb_rotate_right(parent, root);
                node = root->rb_node;
                break;
            }
        }
    }
    if (node)
        node->rb_color = RB_BLACK;
}


static void rb_erase(rb_node_t * node, rb_root_t * root)
{
    rb_node_t * child, * parent;
    int color;

    if (!node->rb_left)
        child = node->rb_right;
    else if (!node->rb_right)
        child = node->rb_left;
    else
    {
        rb_node_t * old = node, * left;

        node = node->rb_right;
        while ((left = node->rb_left))
            node = left;
        child = node->rb_right;
        parent = node->rb_parent;
        color = node->rb_color;

        if (child)
            child->rb_parent = parent;
        if (parent)
        {
            if (parent->rb_left == node)
                parent->rb_left = child;
            else
                parent->rb_right = child;
        }
        else
            root->rb_node = child;

        if (node->rb_parent == old)
            parent = node;
        node->rb_parent = old->rb_parent;
        node->rb_color = old->rb_color;
        node->rb_right = old->rb_right;
        node->rb_left = old->rb_left;

        if (old->rb_parent)
        {
            if (old->rb_parent->rb_left == old)
                old->rb_parent->rb_left = node;
            else
                old->rb_parent->rb_right = node;
        } else
            root->rb_node = node;

        old->rb_left->rb_parent = node;
        if (old->rb_right)
            old->rb_right->rb_parent = node;
        goto color;
    }

    parent = node->rb_parent;
    color = node->rb_color;

    if (child)
        child->rb_parent = parent;
    if (parent)
    {
        if (parent->rb_left == node)
            parent->rb_left = child;
        else
            parent->rb_right = child;
    }
    else
        root->rb_node = child;

color:
    if (color == RB_BLACK)
        __rb_erase_color(child, parent, root);
}



#endif  /* _LINUX_RBTREE_H */



test.c

#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include "rbtree.h"

typedef unsigned int    CORE_ADDR;

typedef struct rb_addr_s {
    rb_node_t   rb_node;
    CORE_ADDR   addr;
}rb_addr_t;

static inline rb_addr_t *
rb_find_addr_struct(CORE_ADDR addr, rb_root_t *root, rb_node_t **ret_parent, rb_node_t ***ret_link)
{
    rb_node_t   **link = &root->rb_node;
    rb_node_t   *parent = NULL;
    rb_addr_t   *rb_addr = NULL;
    rb_addr_t   *ret_rb_addr = NULL;

    while (*link) {
        parent = *link;
        rb_addr = rb_entry(parent, rb_addr_t, rb_node);

        if (addr < rb_addr->addr) {
            link = &(*link)->rb_left;
        }
        else if (addr > rb_addr->addr) {
            link = &(*link)->rb_right;
        }
        else {
            ret_rb_addr = rb_addr;
            break;
        }
    }
    if (ret_parent) {
        *ret_parent = parent;
    }
    if (ret_link) {
        *ret_link = link;
    }

    return(ret_rb_addr);
}


int rb_insert_addr(CORE_ADDR addr, rb_root_t *root)
{
    rb_node_t   **rb_link;
    rb_node_t   *rb_parent;
    rb_addr_t   *rb_addr = NULL;

    if (rb_find_addr_struct(addr, root, &rb_parent, &rb_link)) {
        return(-1);
    }
    rb_addr = (rb_addr_t *)malloc(sizeof(rb_addr_t));
    if (!rb_addr) {
        return(-1);
    }
    rb_addr->addr = addr;
    rb_link_node(&rb_addr->rb_node, rb_parent, rb_link);
    rb_insert_color(&rb_addr->rb_node, root);

    return(0);

}


int rb_remove_addr(CORE_ADDR addr, rb_root_t *root)
{
    rb_addr_t   *rb_addr = rb_find_addr_struct(addr, root, NULL, NULL);

    if (!rb_addr) {
        return(-1);
    }
    rb_erase(&rb_addr->rb_node, root);
    free(rb_addr);

    return(0);
}



static inline int rb_find_addr(CORE_ADDR addr, rb_root_t *root)
{
    rb_node_t   **link = &root->rb_node;
    rb_node_t   *parent = NULL;
    rb_addr_t   *rb_addr;

    while (*link) {
        parent = *link;
        rb_addr = rb_entry(parent, rb_addr_t, rb_node);

        if (addr < rb_addr->addr) {
            link = &(*link)->rb_left;
        }
        else if (addr > rb_addr->addr) {
            link = &(*link)->rb_right;
        }
        else {
            return(1);
        }
    }

    return(0);
}



int main(int argc,char *argv[], char *envp[])
{
    rb_root_t   addr_root;

    addr_root = RB_ROOT;

    //right insert
    printf("right insert\n");
    if (rb_insert_addr(0x1, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xc0028018, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xd014cb68, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0x74697277, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xc00959f8, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0x959f8, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xe3740ffa, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0x31321, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0x765702, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xf123, &addr_root)) {
        printf("rb_insert_addr error\n");
    }

    //wrong insert
    printf("wrong insert\n");
    if (rb_insert_addr(0x1, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xc0028018, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xd014cb68, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0x74697277, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xc00959f8, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0x959f8, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xe3740ffa, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0x31321, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0x765702, &addr_root)) {
        printf("rb_insert_addr error\n");
    }
    if (rb_insert_addr(0xf123, &addr_root)) {
        printf("rb_insert_addr error\n");
    }

    //right find
    printf("right find\n");
    if (rb_find_addr(0x1, &addr_root)) {
        printf("rb_find_addr ok\n");
    }
    if (rb_find_addr(0xc0028018, &addr_root)) {
        printf("rb_find_addr ok\n");
    }
    if (rb_find_addr(0xd014cb68, &addr_root)) {
        printf("rb_find_addr ok\n");
    }
    if (rb_find_addr(0x74697277, &addr_root)) {
        printf("rb_find_addr ok\n");
    }
    if (rb_find_addr(0xc00959f8, &addr_root)) {
        printf("rb_find_addr ok\n");
    }
    if (rb_find_addr(0x959f8, &addr_root)) {
        printf("rb_find_addr ok\n");
    }
    if (rb_find_addr(0xe3740ffa, &addr_root)) {
        printf("rb_find_addr ok\n");
    }
    if (rb_find_addr(0x31321, &addr_root)) {
        printf("rb_find_addr ok\n");
    }
    if (rb_find_addr(0x765702, &addr_root)) {
        printf("rb_find_addr ok\n");
    }
    if (rb_find_addr(0xf123, &addr_root)) {
        printf("rb_find_addr ok\n");
    }

    //wrong find
    printf("wrong find\n");
    if (rb_find_addr(0x0, &addr_root)) {
        printf("rb_find_addr error\n");
    }
    if (rb_find_addr(0xc002801, &addr_root)) {
        printf("rb_find_addr error\n");
    }
    if (rb_find_addr(0xd014cb6, &addr_root)) {
        printf("rb_find_addr error\n");
    }
    if (rb_find_addr(0x7469727, &addr_root)) {
        printf("rb_find_addr error\n");
    }
    if (rb_find_addr(0xc00959f, &addr_root)) {
        printf("rb_find_addr error\n");
    }
    if (rb_find_addr(0x959f, &addr_root)) {
        printf("rb_find_addr error\n");
    }
    if (rb_find_addr(0xe3740ff, &addr_root)) {
        printf("rb_find_addr error\n");
    }
    if (rb_find_addr(0x3132, &addr_root)) {
        printf("rb_find_addr error\n");
    }
    if (rb_find_addr(0x76570, &addr_root)) {
        printf("rb_find_addr error\n");
    }
    if (rb_find_addr(0xf12, &addr_root)) {
        printf("rb_find_addr error\n");
    }

    //right remove
    printf("right remove\n");
    if (rb_remove_addr(0x1, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xc0028018, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xd014cb68, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0x74697277, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xc00959f8, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0x959f8, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xe3740ffa, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0x31321, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0x765702, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xf123, &addr_root)) {
        printf("rb_remove_addr error\n");
    }

    //wrong remove
    printf("wrong remove\n");
    if (rb_remove_addr(0x1, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xc0028018, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xd014cb68, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0x74697277, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xc00959f8, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0x959f8, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xe3740ffa, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0x31321, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0x765702, &addr_root)) {
        printf("rb_remove_addr error\n");
    }
    if (rb_remove_addr(0xf123, &addr_root)) {
        printf("rb_remove_addr error\n");
    }

    return(0);
}

=======================================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

//////////////////////
// supplied by user //
//////////////////////

typedef int KeyType;            // type of key

typedef struct {                // value related to key
    int stuff;
} ValType;

// how to compare keys
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/////////////////////////////////////
// implementation independent code //
/////////////////////////////////////

typedef enum {
    RBT_STATUS_OK,
    RBT_STATUS_MEM_EXHAUSTED,
    RBT_STATUS_DUPLICATE_KEY,
    RBT_STATUS_KEY_NOT_FOUND
} RbtStatus;

typedef enum { BLACK, RED } nodeColor;

typedef struct NodeTag {
    struct NodeTag *left;       // left child
    struct NodeTag *right;      // right child
    struct NodeTag *parent;     // parent
    nodeColor color;            // node color (BLACK, RED)
    KeyType key;                // key used for searching
    ValType val;                // data related to key
} NodeType;

#define SENTINEL &sentinel      // all leafs are sentinels
static NodeType sentinel = { SENTINEL, SENTINEL, 0, BLACK, 0};

static NodeType *root = SENTINEL; // root of red-black tree

static void rotateLeft(NodeType *x) {

    // rotate node x to left

    NodeType *y = x->right;

    // establish x->right link
    x->right = y->left;
    if (y->left != SENTINEL) y->left->parent = x;

    // establish y->parent link
    if (y != SENTINEL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    } else {
        root = y;
    }

    // link x and y
    y->left = x;
    if (x != SENTINEL) x->parent = y;
}

static void rotateRight(NodeType *x) {

    // rotate node x to right

    NodeType *y = x->left;

    // establish x->left link
    x->left = y->right;
    if (y->right != SENTINEL) y->right->parent = x;

    // establish y->parent link
    if (y != SENTINEL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    } else {
        root = y;
    }

    // link x and y
    y->right = x;
    if (x != SENTINEL) x->parent = y;
}

static void insertFixup(NodeType *x) {

    // maintain red-black tree balance
    // after inserting node x

    // check red-black properties
    while (x != root && x->parent->color == RED) {
        // we have a violation
        if (x->parent == x->parent->parent->left) {
            NodeType *y = x->parent->parent->right;
            if (y->color == RED) {

                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                // uncle is BLACK
                if (x == x->parent->right) {
                    // make x a left child
                    x = x->parent;
                    rotateLeft(x);
                }

                // recolor and rotate
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(x->parent->parent);
            }
        } else {

            // mirror image of above code
            NodeType *y = x->parent->parent->left;
            if (y->color == RED) {

                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                // uncle is BLACK
                if (x == x->parent->left) {
                    x = x->parent;
                    rotateRight(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(x->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

// insert new node (no duplicates allowed)
RbtStatus rbtInsert(KeyType key, ValType val) {
    NodeType *current, *parent, *x;

    // allocate node for data and insert in tree

    // find future parent
    current = root;
    parent = 0;
    while (current != SENTINEL) {
        if (compEQ(key, current->key)) 
            return RBT_STATUS_DUPLICATE_KEY;
        parent = current;
        current = compLT(key, current->key) ?
            current->left : current->right;
    }

    // setup new node
    if ((x = malloc (sizeof(*x))) == 0)
        return RBT_STATUS_MEM_EXHAUSTED;
    x->parent = parent;
    x->left = SENTINEL;
    x->right = SENTINEL;
    x->color = RED;
    x->key = key;
    x->val = val;

    // insert node in tree
    if(parent) {
        if(compLT(key, parent->key))
            parent->left = x;
        else
            parent->right = x;
    } else {
        root = x;
    }

    insertFixup(x);

    return RBT_STATUS_OK;

static void deleteFixup(NodeType *x) {

    // maintain red-black tree balance
    // after deleting node x

    while (x != root && x->color == BLACK) {
        if (x == x->parent->left) {
            NodeType *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateLeft (x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rotateRight (w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rotateLeft (x->parent);
                x = root;
            }
        } else {
            NodeType *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateRight (x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rotateLeft (w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rotateRight (x->parent);
                x = root;
            }
        }
    }
    x->color = BLACK;
}

// delete node
RbtStatus rbtErase(NodeType * z) {
    NodeType *x, *y;

    if (z->left == SENTINEL || z->right == SENTINEL) {
        // y has a SENTINEL node as a child
        y = z;
    } else {
        // find tree successor with a SENTINEL node as a child
        y = z->right;
        while (y->left != SENTINEL) y = y->left;
    }

    // x is y's only child
    if (y->left != SENTINEL)
        x = y->left;
    else
        x = y->right;

    // remove y from the parent chain
    x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        root = x;

    if (y != z) {
        z->key = y->key;
        z->val = y->val;
    }


    if (y->color == BLACK)
        deleteFixup (x);

    free (y);

    return RBT_STATUS_OK;
}

// find key
NodeType *rbtFind(KeyType key) {
    NodeType *current;
    current = root;
    while(current != SENTINEL) {
        if(compEQ(key, current->key)) {
            return current;
        } else {
            current = compLT (key, current->key) ?
                current->left : current->right;
        }
    }
    return NULL;
}

// in-order walk of tree
void rbtInorder(NodeType *p, void (callback)(NodeType *)) {
    if (p == SENTINEL) return;
    rbtInorder(p->left, callback);
    callback(p);
    rbtInorder(p->right, callback);
}

// delete nodes depth-first
void rbtDelete(NodeType *p) {
    if (p == SENTINEL) return;
    rbtDelete(p->left);
    rbtDelete(p->right);
    free(p);
}

void displayNode(NodeType *p) {
    printf("%d %d\n", p->key, p->val.stuff);
}

int main(int argc, char **argv) {
    int maxnum, ct;
    KeyType key;
    RbtStatus status;

    // command-line:
    //
    //   rbt 2000
    //      process 2000 records

    NodeType *p;

    maxnum = atoi(argv[1]);

    printf("maxnum = %d\n", maxnum);
    for (ct = maxnum; ct; ct--) {
        key = rand() % 90 + 1;
        if ((p = rbtFind(key)) != NULL) {
            if (p->val.stuff != 10*key) printf("fail val\n");
            status = rbtErase(p);
            if (status) printf("fail: status = %d\n", status);
        } else {
            ValType val;
            val.stuff = 10*key;
            status = rbtInsert(key, val);
            if (status) printf("fail: status = %d\n", status);
        }
    }

    // output nodes in order
    rbtInorder(root, displayNode);

    rbtDelete(root);

    return 0;
}
